package BackTrack;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

import static MyUtils.MHUtils.debug_digui;

/**
 * 思路：
 *      拿/不拿  -> 普回溯
 *
 * 为啥 轻松ac？
 *      [之前的板子总结 + 刚做完 拿/不拿 的 背包问题 有+-题感 ]
 *      1 bT (cI,faSum) faSum关键
 *      2 bT 超1 才 统计 res
 *
 *      3 bT 与 后序 -> 无关！
 *          bT 收集res
 *          后序 每个cur Max
 *
 *      4 本题注意：
 *          2个 同 i+1
 *          -> 1个拿 / 1个不拿
 */
public class 目标和494 {

    // int[][] map; -> 要用map要改写成 后序 -> 想不到..
    public int findTargetSumWays_old(int[] nums, int target) {
        this.nums=nums; t=target;
        backTrack_old(0, 0);
        return count;
    }
    private void backTrack_old(int cI, int faSum) {
        if(cI == nums.length){
            if(faSum == t){
                count++;
            }
            return;
        }

        backTrack_old(cI+1, faSum+nums[cI]);
        backTrack_old(cI+1, faSum-nums[cI]);
    }


    /**
     * 重要思路：
     *      拿/不拿 -> 每层1种！
     *      (要算的, 当前curSum)
     *
     * map 统计位置：
     *      上 1cur
     *
     * 新：
     *     隐蔽 faSum -> map优化
     *
     *     guidege歌 永远的神
     *     daijs给爹价格
     *     用用的神
     *
     *
     */
    int[] nums;
    int t;
    int count=0;
    Map<String, Integer> canshu_targetNum_Map = new HashMap<>();
    public int findTargetSumWays(int[] nums, int target){
        this.nums=nums; t=target;
        return bT(0,0); // 从第一个开始 [ 每层 1 种
        // return count; // map版 应该 r int f ...
    }

    // 【很多余！】 int f 纯粹是 为 优化map弄的
    // -> 内部核心 仍是 从上到下 的 回溯 void
    int step=0;
    private int bT(int cI, int faSum) {
        debug_digui(step++, "cI=" + cI+",faSUM="+faSum);
        if(cI == nums.length){
            if(faSum == t){
                count++;
                debug_digui(--step, "return 1 -> find!");
                return 1;
            }
            debug_digui(--step, "return 0");
            return 0;
        }

        // map - 1cur
        String canshuKey = cI + "," + faSum;
        if(canshu_targetNum_Map.containsKey(canshuKey)){
            debug_digui(--step, "return " + canshu_targetNum_Map.get(canshuKey) + " ( map )");
            return canshu_targetNum_Map.get(canshuKey);
        }

        int L = bT(cI + 1, faSum + nums[cI]); // 自信 (要算的, 当前curSum)
        int R = bT(cI + 1, faSum - nums[cI]);

        int curTargetNum = L+R;
        canshu_targetNum_Map.put(canshuKey, curTargetNum);
        debug_digui(--step, "return " + canshu_targetNum_Map.get(canshuKey));
        return curTargetNum;
    }

    @Test
    public void test() {
        int[] p = new int[]{1,1,1,1,1};
        System.out.println("RES:" + findTargetSumWays(p, 3));
    }
}
